package leetcod_300;

import java.util.*;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 * <p>
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */
public class leetCode_23_Merge_k_SortedLists {

    public static ListNode mergeTwoList(ListNode l1, ListNode l2) {
        ListNode h = new ListNode(0);
        ListNode ans = h;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                h.next = l1;
                h = h.next;
                l1 = l1.next;
            } else {
                h.next = l2;
                h = h.next;
                l2 = l2.next;
            }
        }
        if (l1 == null) {
            h.next = l2;
        }
        if (l2 == null) {
            h.next = l1;
        }
        return ans.next;

    }

    public ListNode mergeKListsByViolented(ListNode[] lists) {
        List<Integer> l = new ArrayList<Integer>();
        //存到数组
        for (ListNode ln : lists) {
            while (ln != null) {
                l.add(ln.val);
                ln = ln.next;
            }
        }
        //数组排序
        Collections.sort(l);
        //存到链表
        ListNode head = new ListNode(0);
        ListNode h = head;
        for (int i : l) {
            ListNode t = new ListNode(i);
            h.next = t;
            h = h.next;
        }
        h.next = null;
        return head.next;
    }

    public ListNode mergeKLists2(ListNode[] lists) {
        //下标
        int min_index = 0;
        ListNode head = new ListNode(0);
        ListNode h = head;
        while (true) {
            boolean isBreak; //标记是否遍历完所有链表
            isBreak = true;
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < lists.length; i++) {
                if (lists[i] != null) {
                    //找出最小下标
                    if (lists[i].val < min) {
                        min_index = i;
                        min = lists[i].val;
                    }
                }
                //存在一个链表不为空，标记改为false
                isBreak = false;
            }
            if (isBreak) {
                break;
            }
            //加载到新链表中
/*            ListNode a = new ListNode(lists[min_index].val);
            h.next = a;*/
            //最小的节点接过来
            h.next = lists[min_index];
            h = h.next;
            //链表后移一个元素
            lists[min_index] = lists[min_index].next;
        }
        h.next = null;
        return head.next;
    }

    /**
     * 时间复杂度 O（N log（k））
     *
     * @param lists
     * @return
     */
    public ListNode mergeKListsByPriorityQueue(ListNode[] lists) {
        //定义优先队列的比较器
        Comparator<ListNode> cmp;
        cmp = new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        };
        //建立队列
        PriorityQueue<ListNode> q = new PriorityQueue<>(cmp);
        for (ListNode l : lists) {
            if (l != null) {
                q.add(l);
            }
        }
        ListNode head = new ListNode(0);
        ListNode point = head;
        while (!q.isEmpty()) {
            //出队列
            point.next = q.poll();
            point = point.next;
            //判断当前链表是否为空 不为空将新元素入队
            ListNode next = point.next;
            if (next != null) {
                q.add(next);
            }
        }
        return head.next;
    }

    /**
     * 两两合并
     *
     * @param lists
     * @return
     */
    public ListNode mergeKListsByPriorityQueueByDivideAndConquer(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        int interval = 1;
        while (interval < lists.length) {
            System.out.println(lists.length);
            for (int i = 0; i + interval < lists.length; i = i + interval * 2) {
                lists[i] = mergeTwoList(lists[i], lists[i + interval]);
            }
            interval *= 2;
        }
        return lists[0];
    }


}
